// 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
// 输入：height = `[0,1,0,2,1,0,1,3,2,1,2,1]`
// 输出：6
// 解释：上面是由数组 `[0,1,0,2,1,0,1,3,2,1,2,1]` 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

// 思路，单调栈
// 单调栈用来寻找任意一个元素右边或者左边第一个比自己大或者小的元素的位置
// 该题用的单调栈的顺序为从栈头开始，从小到大，当遇到大于栈头的元素，此时出现凹槽，栈头元素就是凹槽的底部的柱子，栈头的第二个元素是凹槽左边的柱子，而添加的元素就是凹槽右边的柱子
// 遇到相同的柱子也应该弹出栈头，更新下标，因为我们计算宽度需要用最右边的柱子
// 栈里只需要保存下标，通过下标获取高度
// 有三种情况
// 1. 当前元素高度小于栈顶元素的高度，把当前元素下标放入栈中

// 2. 当前元素高度等于栈顶元素的高度，放入栈中

// 3. 当前元素高度大于栈顶元素的高度，出现凹槽，弹出栈顶，标记为mid，即为凹槽底部高度，当前栈顶即为底部左侧高度，当前元素即为底部右侧高度

function trap(height) {
    let sum = 0
    let stack = [0]
    for (let i = 0; i < height.length; i++) {
        while (stack.length && height[i] > height[stack[0]]) {
            let mid = stack.shift()
            if (stack.length) {
                let left = stack[0]
                let h = Math.min(height[i], height[left]) - height[mid]
                let w = i - left - 1
                sum += h * w
            }
        } 
        stack.unshift(i)       
    }
    return sum
}

let height = [0,1,0,2,1,0,1,3,2,1,2,1]
console.log(trap(height))

// 思路2， 暴力解法
// 每一列雨水的高度，取决于该列左侧最高的柱子和该列右侧最高的柱子中最矮的那个和该列的高度差
// 我们遍历所有的列，第一个和最后一个柱子不接雨水
function trap2(height) {
    let sum = 0
    let maxLeft = new Array(height.length).fill(0)
    let maxRight = new Array(height.length).fill(0)
    maxLeft[0] = height[0]
    for (let i = 1; i < height.length; i++) {
        maxLeft[i] = Math.max(maxLeft[i - 1], height[i])
    }
    maxRight[maxRight.length - 1] = height[height.length - 1]
    for (let i = height.length - 2; i >= 0; i--) {
        maxRight[i] = Math.max(maxRight[i + 1], height[i])     
    }
    for (let i = 1; i < height.length - 1; i++) {
        let h = Math.min(maxLeft[i], maxRight[i]) - height[i]
        if (h > 0) {
            sum += h
        }
    }
    return sum
}

console.log(trap2(height))